const { countingSort } = require("./7counting.js");

/**
 * 桶排序
 *
 * @param {number[]} nums
 * @return {number[]}
 */
function bucketSort(nums) {
  const length = nums.length;
  if (length < 2) {
    return nums;
  }
  let min = nums[0];
  let max = nums[0];
  for (let i = 1; i < length; i++) {
    min = Math.min(min, nums[i]);
    max = Math.max(max, nums[i]);
  }
  const bucket = 10;
  const size = Math.ceil((max - min) / bucket + 1);
  const list = [];
  for (let i = 0; i < size; i++) {
    list.push([]);
  }
  for (let i = 0; i < length; i++) {
    list[Math.floor((nums[i] - min) / bucket)].push(nums[i]);
  }
  for (let i = 0; i < size; i++) {
    list[i] = countingSort(list[i]);
  }
  return [].concat(...list);
}

const nums = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(bucketSort(nums));
